package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

/**
 * {@link LC76_4}
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/
 * 没有重复字符的最长子串.
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC3 extends LC76_4 implements TwoProblem {
    public int lengthOfLongestSubstring(String s) {
        int[] xx = new int[128];//可以理解为path, 这道题xx里每个字母的次数, 一般为0,1, 最大为2, 只有一个可能出现2
        int slow = 0, fast = 0, longest = 0;//叫做slow/fast begin/end left/right都可, 左闭右开
        boolean valid = true;
        while (fast < s.length()) {
            char c1 = s.charAt(fast);
            if (xx[c1] == 1) {//已经有了
                valid = false;
            }
            xx[c1]++;
            fast++;
            if (valid) {
                longest = Math.max(longest, fast - slow);
            }
            while (!valid) {//当不valid的时候移动left使之重新valid
                char c2 = s.charAt(slow);
                if (xx[c2] == 2)
                    valid = true;
                xx[c2]--;
                slow++;
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        System.out.println(new LC3().lengthOfLongestSubstring("abcade"));
        System.out.println(new LC3().lengthOfLongestSubstring("aa"));
        System.out.println(new LC3().lengthOfLongestSubstring("mlgpabcade"));
    }
}
